package com.zk.algorithm.string;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.Arrays;

/**
 * @author zk
 */
@LeetCodeExplore
@Easy
public class LongestCommonPrefix {

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        // ======================
        // 排序
        // ======================
        // O(nlogn)
        Arrays.sort(strs);

        // flight
        // flow
        // flower
        char[] first = strs[0].toCharArray();
        char[] last = strs[strs.length - 1].toCharArray();

        // ======================
        // 比较第一个和最后一个字符串
        // ======================

        int i = 0, len = Math.min(first.length, last.length);
        // O(n)
        while (i < len && first[i] == last[i])
            i++;

        return strs[0].substring(0, i);
    }

}
